﻿//1753. 移除石子的最大得分
//
//你正在玩一个单人游戏，面前放置着大小分别为 a​​​​​​、b 和 c​​​​​​ 的 三堆 石子。
//
//每回合你都要从两个 不同的非空堆 中取出一颗石子，并在得分上加 1 分。当存在 两个或更多 的空堆时，游戏停止。
//
//给你三个整数 a 、b 和 c ，返回可以得到的 最大分数 。
//
//示例 1：
//
//输入：a = 2, b = 4, c = 6
//输出：6
//解释：石子起始状态是(2, 4, 6) ，最优的一组操作是：
//- 从第一和第三堆取，石子状态现在是(1, 4, 5)
//- 从第一和第三堆取，石子状态现在是(0, 4, 4)
//- 从第二和第三堆取，石子状态现在是(0, 3, 3)
//- 从第二和第三堆取，石子状态现在是(0, 2, 2)
//- 从第二和第三堆取，石子状态现在是(0, 1, 1)
//- 从第二和第三堆取，石子状态现在是(0, 0, 0)
//总分：6 分 。

class Solution {
public:
    int maximumScore(int a, int b, int c) {
        vector<int> curarr = { a, b, c };
        sort(curarr.begin(), curarr.end());
        int ret = 0;
        ret += curarr[1] - curarr[0];
        curarr[1] = curarr[0];
        curarr[2] -= ret;
        int diff = curarr[2] - curarr[1];
        int maxstep = min({ diff, curarr[1], curarr[2] / 2 });
        ret += maxstep * 2;
        curarr[0] -= maxstep;
        curarr[1] = curarr[0];
        curarr[2] -= maxstep * 2;
        if (maxstep == diff) {
            ret += curarr[0] / 2 * 3;
            if (curarr[0] % 2) {
                ret++;
            }
        }
        else if (maxstep == curarr[2] / 2) {
            ret += curarr[0];
            if (curarr[2] && curarr[1]) {
                ret++;
            }
        }
        return ret;
    }
};



//1690. 石子游戏 VII
//石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。
//有 n 块石子排成一排。每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头，
//并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时，得分较高者获胜。
//鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。
//给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值
//
//示例 1：
//
//输入：stones = [5, 3, 1, 4, 2]
//输出：6
//解释：
//- 爱丽丝移除 2 ，得分 5 + 3 + 1 + 4 = 13 。游戏情况：爱丽丝 = 13 ，鲍勃 = 0 ，石子 = [5, 3, 1, 4] 。
//- 鲍勃移除 5 ，得分 3 + 1 + 4 = 8 。游戏情况：爱丽丝 = 13 ，鲍勃 = 8 ，石子 = [3, 1, 4] 。
//- 爱丽丝移除 3 ，得分 1 + 4 = 5 。游戏情况：爱丽丝 = 18 ，鲍勃 = 8 ，石子 = [1, 4] 。
//- 鲍勃移除 1 ，得分 4 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [4] 。
//- 爱丽丝移除 4 ，得分 0 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [] 。
//得分的差值 18 - 12 = 6

class Solution {
public:
    int stoneGameVII(vector<int>& stones) {
        int n = stones.size();
        vector<int> presum(n + 1);
        // for(int i = 0; i < n; ++i){
        //     presum[i + 1] = presum[i] + stones[i];
        // }
        // function<int(int, int)> dfs = [&](int left, int right) -> int{
        //     if(left == right){
        //         return 0;
        //     }
        //     return max(presum[right + 1] - presum[left + 1] - dfs(left + 1, right), presum[right] - presum[left] - dfs(left, right - 1));
        // };
        // return dfs(0, n - 1);

        // dp[i][j]表明 stones[i][j]的操作结果
        // dp[i][j] = max(a - dp[i + 1][j], b - dp[i][j - 1]);
        // 3, 5 = 4, 5 he 3, 4
        // 
        // vector<vector<int>> dp(n, vector<int> (n));
        // for(int j = 0; j < n; ++j){
        //     for(int i = j - 1; i >= 0; --i){
        //         if(i + 1 == j){
        //             dp[i][j] = max(stones[i], stones[j]);
        //         }
        //         else{
        //             dp[i][j] = max(presum[j + 1] - presum[i + 1] - dp[i + 1][j], presum[j] - presum[i] - dp[i][j - 1]);
        //         }
        //     }
        // }
        // return dp[0][n - 1];

        vector<int> dp(n);
        for (int j = 0; j < n; ++j) {
            presum[j + 1] = presum[j] + stones[j];
            for (int i = j - 1; i >= 0; --i) {
                if (i + 1 == j) {
                    dp[i] = max(stones[i], stones[j]);
                }
                else {
                    dp[i] = max(presum[j + 1] - presum[i + 1] - dp[i + 1], presum[j] - presum[i] - dp[i]);
                }
            }
        }
        return dp[0];
    }
};

